package com.learn;

import java.util.Arrays;

public class mergeSort {
    public static int[] mergeSort(int[] array) {
        if (array.length < 2) {
            return array;
        }
        int middle = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, middle);
        int[] right = Arrays.copyOfRange(array, middle, array.length);
        int[] leftSorted=mergeSort(left);
        int[] rightSorted=mergeSort(right);
        return merge(leftSorted, rightSorted);
    }

    public static int[] merge(int[] left, int[] right) {
        int[] newArray = new int[left.length + right.length];
        int lindex = 0;
        int rindex = 0;
        for (int i = 0; i < newArray.length; i++) {
            if (lindex >= left.length) {
                newArray[i] = right[rindex++];
            } else if (rindex >= right.length) {
                newArray[i] = left[lindex++];
            } else if (left[lindex] < right[rindex]) {
                newArray[i] = left[lindex++];
            } else {
                newArray[i] = right[rindex++];
            }
        }
        return newArray;
    }

    public static void main(String[] args) {
        int[] array = {2, 1, 7, 3, 7, 9, 5};
        System.out.println(Arrays.toString(mergeSort(array)));
    }
}
